Алгоритм Марзулло

Алгоритм Марзулло — это алгоритм согласования данных, использующийся для выбора более точных источников для оценки точного времени из ряда источников времени, разной степени точности и усреднения времени, полученными от разных NTP-серверов. Переработанная версия этого алгоритма, названная «алгоритмом пересечений», является частью сетевого протокола для синхронизации времени (NTP).

Изобретён Кейтом Марзулло в рамках своей кандидатской диссертации в 1984 году.

Алгоритм позволяет сводить к минимуму влияние данных от заведомо некорректно настроенных NTP-серверов на общую систему.

Описание

Алгоритм Марзулло эффективен (в терминах времени) для получения оптимального значения из множества оценок с их доверительными интервалами. Важно, что для некоторых источников оптимальное значение может лежать вне доверительного интервала. Наилучшей оценкой следует считать наименьший интервал, соответствующий наибольшему числу источников.

Предположим, что мы имеем следующие оценки: 10 ± 2, 12 ± 1 и 11 ± 1 в интервалах [8,12], [11,13] и [10,12]. Их пересечением будет интервал [11,12] или точка 11.5 ± 0.5, соответствующая всем трём источникам.

Алгоритм Марзулло, пример

Распишем алгоритм по шагам:

1. Построить таблицу кортежей. Каждый кортеж является парой: смещение и тип. Смещение содержит значение времени для начала или конца интервала, тип равен -1 для начала и +1 для конца. Таким образом, для каждого интервала добавляется два кортежа, по одному для начала и конца.
2. Сортировать таблицу по не убыванию смещения. (В случае одинакового смещения для двух кортежей противоположных типов (один интервал заканчивается с началом другого) применить специальный метод разрешения приоритета
3. [инициализация] best=0 cnt=0
4. [цикл] идти по таблице кортежей в порядке возрастания

4. [текущий номер перекрывающихся интервалов] cnt=cnt−type[i]
5. если cnt>best тогда best=cnt beststart=offset[i] bestend=offset[i+1]

комментарий: следующий кортеж [i+1] будет либо концом интервала с типом type=+1, что означает что это конец наилучшего на этот момент интервала или будет началом интервала с типом type=−1, который на следующем шаге станет лучшим.

6. [конец цикла] запомнить и вернуть интервал из кортежа [beststart, bestend] как оптимальный.

Количество ложных (не пересекающихся с определённым оптимальным интервалом) источников определить как общее количество источников за вычетом наилучших отобранных.

См. также

•  (англ.)Intersection algorithm (алгоритм пересечений)

Литература

• K. A. Marzullo. Maintaining the Time in a Distributed System: An Example of a Loosely-Coupled Distributed Service. Ph.D. dissertation, Stanford University, Department of Electrical Engineering, February 1984.
• IEEE STANDARD 1588—2008 — IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems

Ссылки

•  (англ.)Домашняя страница Кейта Марзулло
•  (англ.)Давид Л. Миллз, Краткая история NTP
• Синхронизация времени
• Обеспечение высокоточной временной синхронизации в распределённых вычислительных системах, Б. В. Усков
• Система точного времени NTP на сайте Рязанского государственного университета
• Marzullo’s algorithm — in java